PROBLEM:

Expedition    exp.X

A group of cows grabbed a truck and ventured on an expedition deep into the jungle. Being rather poor drivers, the cows unfortunately managed to run over a rock and puncture the truck's fuel tank. The truck now leaks one unit of fuel every unit of distance it travels.

To repair the truck, the cows need to drive to the nearest town (no more than 10,000,000 units distant) down a long, winding road. On this road, between the town and the current location of the truck, there are N (1 <= N <= 50,000) fuel stops where the cows can stop to acquire additional fuel. The i-th fuel stop is a distance of D_i (1 <= D_i < L) from the town, and contains F_i (1 <= F_i <= 100) fuel.

The jungle is a dangerous place for humans and is especially dangerous for
cows. Therefore, the cows want to make the minimum possible number of stops
for fuel on the way to the town. Fortunately, the capacity of the fuel tank
on their truck is so large that there is effectively no limit to the amount
of fuel it can hold. The truck is currently L units away from the town and
has P units of fuel (1 <= P <= 10,000,000).

Determine the minimum number of stops needed to reach the town, or if the
cows cannot reach the town at all. Note that it is possible for there to be
multiple fuel stops at the same location, but they should be counted
separately in the total number of stops.

PROBLEM NAME: exp.X

INPUT FORMAT:

* Line 1: Three space-separated integers: N, L, and P.

* Lines 2..N+1: Line i+1 contains the two integers D_i and F_i.

SAMPLE INPUT:

4 25 10
4 4
5 2
11 5
15 10

INPUT DETAILS:

The truck is 25 units away from the town; the truck has 10 units of fuel. 
Along the road, there are 4 fuel stops at distances 4, 5, 11, and 15 from
the town (so these are initially at distances 21, 20, 14, and 10 from the
truck).  These fuel stops can supply up to 4, 2, 5, and 10 units of fuel,
respectively.

OUTPUT FORMAT:

* Line 1: A single integer giving the minimum number of fuel stops
        necessary to reach the town.  If it is not possible to reach
        the town, output -1.

SAMPLE OUTPUT:

2

OUTPUT DETAILS:

Drive 10 units, stop to acquire 10 more units of fuel, drive 4 more units,
stop to acquire 5 more units of fuel, then drive to the town.

========================== SOLUTION ==================================

The way to solve this problem is to use a kind of greedy approach. First, one needs to add the town as a stop. One does this by adding a single gas station, with fuel 0 at distance 0. This is the ultimate goal; when we've reached it, we're done. We now sort the list of gas stations in order of decreasing distance from the town. That is, the farthest gas station from the town is the first in the list, and the town is last. Thus, the first gas station in the list is the first that we will hit.

Now, here's how we run the algorithm. We drive past as many gas stations as we can. For each gas station we pass, we append the amount of gasoline to a list that we call reach (for bonus points, make this a priority queue sorted by fuel amount).

Eventually, assuming we don't reach the town first, we will hit negative gas trying to reach another gas station. As soon as this happens, we start retroactively emptying the gas stations that we have already passed, and removing them from reach. We always take gas from the largest available station, because it is disadvantageous to take less gas than we possibly can. Each time we empty a station, we increment a stops counter, which begins at 0.

If we are able to get back up to a positive fuel level again, we add the next gas station to reach, update our location, and continue on our journey. If we cannot, then we have run out of gas, and even emptying all of the previous gas stations will not be enough to get us beyond our last stop. So, we print -1 and return, per the problem instructions.

Because the last gas station on the list is the town, if we reach the last gas station, then by definition we can reach the town. We then print number of stops it took us to get there, and we're done!

============================ CODE ====================================

# in Python

def paircmp(x, y): # for sorting the gas stations by distance
    return x[0] - y[0]

def main():
    [N, L, P] = map(int, raw_input().split())
    stations = []
    for i in range(N):
        stations.append(map(int, raw_input().split()))
        

    stations = sorted(pairs, paircmp)
    stations.reverse()
    stations.append([0, 0])
    
    fuel = P    # amount of fuel in our tank
    reach = []  # gas stockpiles we can reach
    stops = 0   # the number of gas stops we've made
    curx = L    # our current location
    
    # we travel one gas station at a time
    for station in stations:
        fuel -= abs(curx - pair[0]) # at each step, subtract the fuel 					      # we would lose
        if fuel < 0:

            while len(reach) > 0 and fuel < 0: 
		#while we still have negative fuel and still have gas 
	      #stations that we can empty
                m = max(reach)  # find the biggest gas depot
                fuel += m	  # add its fuel to our tank
                reach.remove(m) # remove it from the list as empty
                stops += 1 	  # note that we stopped

            if fuel < 0:	  
		# if at the end of the above loop we're still out of gas, 
		# we can't reach the town, so we print -1 and return.
                print -1
                return;

        reach.append(station[1]) # we only append this if we actually 
				         # have enough fuel to reach it
        curx = pair[0]

    print stops
    

if __name__ == "__main__":
    main()